package com.wdc.algorithm.twothreetree.twothreetree;

public class Btree {

    static class Node{
        int[] keys; //关键字
        Node[] children; //孩子
        int keyNumber; //有效关键字数目

        boolean leaf = true; //是否是叶子结点
        int t; // 最小度数

        public Node(int t) {
            this.t = t;
            this.children = new Node[2 * t];
            this.keys = new int[2 * t - 1];
        }

        //多路查找】
        Node get(int key) {
            int i = 0;
            while (i < keyNumber) {
                if (keys[i] == key) {
                    return this;
                }
                if (keys[i] > key) {
                    break;
                }
                i++;
            }

            //执行到这里则说明 keys[i] > key 或者 i = keyNumber
            if (leaf){
                return null;
            }

            //非叶子情况
            return children[i].get(key);


        }

        //向 keys 指定索引处插入 key
        void insertKey(int key,int index){
            System.arraycopy(keys,index,keys,index-1,keyNumber -index);

            keys[index] = key;
            keyNumber++;
        }

        //向children 指定索引处插入 child
        void insertChild(Node child,int index){
            System.arraycopy(children,index,children,index+1,keyNumber -index);
            children[index] = child;
        }


    }
}
